<?php
/**
 * @title 2653. 滑动子数组的美丽值
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @param Integer $x
     * @return Integer[]
     */
    function getSubarrayBeauty($nums, $k, $x) {
        /**
         * @since 2024-05-23 取k个元素出来，排序
         */
        $numArray = array_slice($nums, 0, $k);
        sort($numArray);

        /**
         * @since 2024-05-23 分成3块，第x小的元素，比x小的元素集合，比x大的元素集合
         */
        $xMin = $numArray[$x-1];
        $minArray = $maxArray = [];
        for($right=0; $right<$x-1; $right++){
            $num = $numArray[$right];
            $minArray[$num] = ($minArray[$num] ?? 0) + 1;
        }
        $xMin = $numArray[$right++];
        for(; $right<$k; $right++){
            $num = $numArray[$right];
            $maxArray[$num] = ($maxArray[$num] ?? 0) + 1;
        }

        /**
         * @since 2024-05-23 请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值
         * @since 2024-05-23 移动窗口
         */
        $result = [];
        $result[] = min(0, $xMin);
        for($left=0; $right<count($nums); $left++, $right++){
            /**
             * @since 2024-05-23 端水大师开始
             */
            $leftNum = $nums[$left];
            $rightNum = $nums[$right];
            // echo "left: $leftNum, right: $rightNum, xMin: $xMin, minArray: ". json_encode($minArray) .", maxArray: ". json_encode($maxArray) ."\n";

            /**
             * @since 2024-05-23 left就是第x小值
             */
            if($leftNum == $xMin){
                if($rightNum == $xMin){
                } elseif($rightNum > $xMin){
                    /**
                     * @since 2024-05-23 max数量多了1个，最小值变中间值
                     */
                    $maxArray[$rightNum] = ($maxArray[$rightNum] ?? 0) + 1;
                    list($xMin, $maxArray) = self::popMin($maxArray);
                } elseif($rightNum < $xMin){
                    /**
                     * @since 2024-05-23 min数量多了1个，最大值变中间值
                     */
                    $minArray[$rightNum] = ($minArray[$rightNum] ?? 0) + 1;
                    list($xMin, $minArray) = self::popMax($minArray);
                } else {}
            } elseif($leftNum > $xMin){
                /**
                 * @since 2024-05-23 left移出，max数量减1
                 * @since 2024-05-23 right>=x, max数量加1
                 */
                if($maxArray[$leftNum] == 1){
                    unset($maxArray[$leftNum]);
                } else {
                    $maxArray[$leftNum]--;
                }
                if($rightNum >= $xMin){
                    $maxArray[$rightNum] = ($maxArray[$rightNum] ?? 0) + 1;
                } elseif($rightNum < $xMin){
                    /**
                     * @since 2024-05-23 min数量加1，中间值放到max，min最大值变中间值
                     */
                    $maxArray[$xMin] = ($maxArray[$xMin] ?? 0) + 1;
                    $minArray[$rightNum] = ($minArray[$rightNum] ?? 0) + 1;
                    list($xMin, $minArray) = self::popMax($minArray);
                } else {}
            } elseif($leftNum < $xMin){
                /**
                 * @since 2024-05-23 left移出，min数量减1
                 * @since 2024-05-23 right<x, min数量加1
                 */
                if($minArray[$leftNum] == 1){
                    unset($minArray[$leftNum]);
                } else {
                    $minArray[$leftNum]--;
                }
                if($rightNum < $xMin){
                    $minArray[$rightNum] = ($minArray[$rightNum] ?? 0) + 1;
                } elseif($rightNum >= $xMin){
                    /**
                     * @since 2024-05-23 max数量加1，中间值放到min，max最小值变中间值
                     */
                    $maxArray[$rightNum] = ($maxArray[$rightNum] ?? 0) + 1;
                    $minArray[$xMin] = ($minArray[$xMin] ?? 0) + 1;
                    list($xMin, $maxArray) = self::popMin($maxArray);
                }
            } else {}
            $result[] = min(0, $xMin);
        }

        /**
         * @return
         */
        return $result;
    }

    /**
     * @title 弹出一个最大值
     * @author start2004
     * @since 2024-05-23 Created
     *
     * @param Array $nums
     * @return [Int, Array]
     */
    function popMax($nums){
        $max = max(array_keys($nums));
        if($nums[$max] == 1){
            unset($nums[$max]);
        } else {
            $nums[$max]--;
        }

        return [$max, $nums];
    }

    /**
     * @title 弹出一个最小值
     * @author start2004
     * @since 2024-05-23 Created
     *
     * @param Array $nums
     * @return [Int, Array]
     */
    function popMin($nums)
    {
        $min = min(array_keys($nums));
        if ($nums[$min] == 1) {
            unset($nums[$min]);
        } else {
            $nums[$min]--;
        }

        return [$min, $nums];
    }
}


/**
 * @url http://127.0.0.1/leetcode/202405/2024.05.23_2.php
 */
$datas = [
    // [[1,-1,-3,-2,3], 3, 2], // -1,-2,-2
    [[-30,28,34,-15,-13], 2, 2], // 0,0,0,-13
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    /**
     * @since 2024-01-15 超时和错误案例参数
     */
    // $data = $xhprof->FormatArgs("/tmp/leetcode/xxx-xxx.txt");

    // $data[0] = $xhprof->listNode($data[0]);
    // $data[0] = $xhprof->tree($data[0]);
    echo $xhprof->DumpArgs($data);
    echo "\n<hr>\n";

    $obj = new Solution();
    $result = $obj->getSubarrayBeauty(...$data);
    echo $xhprof->DumpArgs([$result]);
    var_dump($result);

    echo "\n<hr>". str_repeat("<br>", 2) . str_repeat(PHP_EOL, 5);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $func = $data[0][$i];
//         $param = $data[1][$i];
//         $result = $obj->$func(...$param);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
